//
// Created by Administrator on 2023/9/4.
// 不用乘除求余, 计算整数除法
// https://leetcode.cn/problems/divide-two-integers/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
// 算小点的数没问题, 在LeetCode上没通过, 原因是int溢出

#include <iostream>
#include <ctime>

using namespace std;

// 被除数a右移 从右移30开始到0
// 为什么要从30开始到0, 不能反过来从0到30?
// 因为要将b向左移到最接近a,然后a-b
int divide02(int a, int b)
{
    int ret = 0;
    int aa = a >= 0 ? a : ~a + 1;
    int bb = b >= 0 ? b : ~b + 1;
    // 用循环判定
    for (int i = 30; i >= 0; --i)
    {
        if ((aa >> i) >= bb)
        {
            ret |= (1 << i);
            aa -= (bb << i);
        }
    }
    if ((a < 0) ^ (b < 0))
        return ~ret + 1;
    return ret;
}

// a:dividend被除数 b: divisor除数
// 除数b左移 这个方法不好 如果被除数a太大, 会溢出
int divide01(int a, int b)
{
    bool negative = false;
    if ((a > 0) ^ (b > 0))
        negative = true;
    a = a >= 0 ? a : ~a + 1;
    b = b >= 0 ? b : ~b + 1;
    if (a == b and !negative)
        return 1;
    else if (a == b and negative)
        return -1;
    else if (a < b)
        return 0;
    int ans = 0, aa = a, bb = b;
    while (aa >= b)
    {
        int t = 0;
        // 如果a是int最大值, bb<<1就会溢出
        while ((bb << 1) <= aa)
        {
            bb <<= 1;
            t++;
        }
//        cout<<t<<endl;
        ans |= (1 << t);
        aa -= bb;
        bb = b;
    }
    if (negative)
        return ~ans + 1;
    return ans;
}

int divide03(int a, int b)
{
    int ret, MIN = -2147483648;
    if (b==1)
        return a;
    else if (a == MIN && b == MIN)
    {
        return 1;
    } else if (b == MIN)
    {
        return 0;
    }else if (a==MIN)
    {
        a=~(a+1)+1; //最小值加一 再取绝对值
        int bb = b<0?~b+1:b;
        int n = divide02(a, bb);
        int t = n * bb; // 还原回去, 看看和最小值差多少
        int tt = ~(MIN + t )+1;
        if (divide02(tt, bb)>=1)
        {
            ret= n+1;
        } else
            ret = n;
        if (b>0)
            ret = ~ret+1;
    } else{
        ret = divide02(a,b);
    }
    return ret;
}

int main()
{
    int a = 20, b = 5, MIN = -2147483648;
//    a=-1,b=1;
    a=-2147483648,b=2;
//    srand((int) time(0));
//    a=rand()*rand();
//    b=rand();
    printf("%d/%d=%d\n", a, b, a / b);
    cout << divide01(a, b) << endl;
    cout << divide02(a, b) << endl;
    cout << divide03(a, b) << endl;
    return 0;
}


